/**
 * Copyright 2011 Tian Zhu <jrash06@gmail.com>
 * 
 * This file is part of java-object-pool.
 *
 * java-object-pool is free software: you can redistribute it and/or modify
 * it under the terms of the Lesser GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * java-object-pool is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * Lesser GNU General Public License for more details.
 *
 * You should have received a copy of the Lesser GNU General Public License
 * along with java-object-pool.  If not, see <http://www.gnu.org/licenses/>.
 */
package net.sf.javaobjectpool;

import java.util.Arrays;

/**
 * cache recyclable objects and allocate previously cached one for reuse <p>
 * 
 * one global pool is created together with several local pools, one pool per
 * thread, in order to achieve non-synchronized caching and allocating for the
 * most of times, and synchronized operations when local pool is empty in case
 * of allocating, or full in case of recycling. <p>
 * 
 * Tune the globalSize and localSize parameters to set the size of global pool
 * and the size of each per thread local pool, so as to achieve the desired
 * trade-off between memory cost on cached objects and synchronization overhead.
 */
public abstract class ObjectPool<T> {
	/** default local pool size */
	static final int DEFAULT_LOCAL_CACHE_SIZE = 1000;

	/** global pool size */
	final int GLOBAL_CACHE_SIZE;

	/** per thread pool size */
	final int LOCAL_CACHE_SIZE;

	/** global pool */
	private Pool<T> globalPool;

	/** per thread pools */
	private ThreadLocal<Pool<T>> localPools;

	/**
	 * the object that represents a pool, either a local or a global one
	 */
	private static class Pool<T> {
		/** the array used for storing cached objects */
		private T[] cache;

		/** next slot of cached object for allocating */
		private volatile int nextAllocIdx = -1;

		private Pool(T[] initCache) {
			this.cache = initCache;
		}
	}

	/**
	 * constructs a pool with specified parameters
	 * 
	 * @param globalSize	set the global pool size
	 * @param localSize		set per thread pool size
	 */
	protected ObjectPool(int globalSize, int localSize) {
		GLOBAL_CACHE_SIZE = globalSize;
		LOCAL_CACHE_SIZE = localSize;
	}

	/**
	 * constructs a pool with default local pool size (=1000) and unlimited
	 * global pool size
	 */
	protected ObjectPool() {
		this(Integer.MAX_VALUE, DEFAULT_LOCAL_CACHE_SIZE);
	}

	/** override this method to implement the array creation */
	protected abstract T[] createObjectArray(int len);

	/** override this method to implement object creation */
	protected abstract T createObject();

	/**
	 * init the pool with the local and global pool size configured,
	 * must be called before using the pool
	 */
	protected final void init() {
		int initialSize = LOCAL_CACHE_SIZE;
		if (initialSize > GLOBAL_CACHE_SIZE)
			initialSize = GLOBAL_CACHE_SIZE;
		globalPool = new Pool<T>(createObjectArray(initialSize));
		localPools = new ThreadLocal<Pool<T>>();
	}

	/**
	 * try to allocate a cached instance from the pool
	 * <p>
	 * 
	 * if the pool is empty, return null; if there is one, either in local pool
	 * or in global pool, return it and free its reference in the pool.
	 */
	public final T allocate() {
		Pool<T> localPool = getLocalPool();
		int localIdx = localPool.nextAllocIdx;

		// if local pool is empty, try to move a chunk from global pool
		if (localIdx < 0) {
			int globalIdx = globalPool.nextAllocIdx;

			// fast, non-synchronized polling of global pool
			// if empty, then give up trying to allocate from the pool
			if (globalIdx < 0)
				return createObject();

			synchronized (globalPool) {
				// check again, as someone else might have exhausted the global
				// pool after the polling above
				globalIdx = globalPool.nextAllocIdx;
				if (globalIdx < 0)
					return createObject();

				// move at most LOCAL_CACHE_SIZE objects from global pool
				int copySize = globalIdx + 1;
				if (copySize > LOCAL_CACHE_SIZE)
					copySize = LOCAL_CACHE_SIZE;
				globalIdx = globalIdx - copySize;
				System.arraycopy(globalPool.cache, globalIdx + 1,
						localPool.cache, 0, copySize);
				Arrays.fill(globalPool.cache, globalIdx + 1, globalIdx
						+ copySize + 1, null);

				localIdx += copySize;
				globalPool.nextAllocIdx = globalIdx;
			}
		}

		/*
		 * allocate from local pool: either the local pool is non-empty at
		 * first, or we have moved a chunk from global pool
		 */
		T o = localPool.cache[localIdx];
		localPool.cache[localIdx] = null;
		localIdx--;
		localPool.nextAllocIdx = localIdx;
		return o;
	}

	/**
	 * try to recycle an object into pool <p>
	 * 
	 * if both local pool and global pool are full, simply discard the passed
	 * object; otherwise, cache it in the pool by setting its reference in the
	 * pool's cache array. <p>
	 * 
	 * @param o
	 *            - the object to recycle
	 * @return - true if successful; false if pool is full and cannot
	 *         accommodate more
	 */
	public final boolean recycle(T o) {
		Pool<T> localPool = getLocalPool();
		int localIdx = localPool.nextAllocIdx;

		// if local pool is full, try move to global pool
		if (localIdx == 2 * LOCAL_CACHE_SIZE - 1) {
			int globalIdx = globalPool.nextAllocIdx;

			// fast, non-synchronized polling of global pool; if full, give up
			// trying
			if (globalIdx == GLOBAL_CACHE_SIZE - 1)
				return false;

			synchronized (globalPool) {
				// check again, as someone else might have made the global pool
				// full after the polling above
				globalIdx = globalPool.nextAllocIdx;
				if (globalIdx == GLOBAL_CACHE_SIZE - 1)
					return false;

				// move at most LOCAL_CACHE_SIZE objects to global pool
				int copySize = GLOBAL_CACHE_SIZE - globalIdx - 1;
				if (copySize > LOCAL_CACHE_SIZE)
					copySize = LOCAL_CACHE_SIZE;

				// ensure global pool's capacity
				if (globalIdx + copySize >= globalPool.cache.length) {
					int newSize = globalPool.cache.length * 2;
					if (newSize > GLOBAL_CACHE_SIZE)
						newSize = GLOBAL_CACHE_SIZE;
					resize(globalPool,newSize);
				}

				System.arraycopy(localPool.cache, LOCAL_CACHE_SIZE * 2
						- copySize, globalPool.cache, globalIdx + 1, copySize);
				Arrays.fill(localPool.cache, LOCAL_CACHE_SIZE * 2 - copySize,
						LOCAL_CACHE_SIZE * 2, null);

				globalIdx += copySize;
				localIdx -= copySize;

				globalPool.nextAllocIdx = globalIdx;
			}
		}

		/*
		 * recycle locally: either the local pool is not full at first, or we
		 * have moved a chunk to global pool
		 */
		localIdx++;
		localPool.cache[localIdx] = o;
		localPool.nextAllocIdx = localIdx;
		return true;
	}

	/**
	 * find the local pool used by the current thread; if not exist, allocate a
	 * new one
	 * 
	 * @return the pool reserved by the current thread
	 */
	private Pool<T> getLocalPool() {
		Pool<T> localPool = localPools.get();
		if (localPool == null) {
			localPool = new Pool<T>(createObjectArray(LOCAL_CACHE_SIZE*2));
			localPools.set(localPool);
		}
		return localPool;
	}
	
	/**
	 * resize the Pool object
	 */
	private void resize(Pool<T> pool, int newSize) {
		T[] newCache = createObjectArray(newSize);
		T[] oldCache = pool.cache;
		int copySize = oldCache.length < newSize ? oldCache.length : newSize;
		System.arraycopy(oldCache, 0, newCache, 0, copySize);
		Arrays.fill(oldCache, null);
		pool.cache = newCache;
	}
}
